This paper considers the problem of scheduling a chain of n coarse-grained tasks on a linear array of k reconfigurable FPGAs\r\nwith the objective of primarily minimizing reconfiguration time. A high-level meta-algorithm along with two detailed metaalgorithms\r\n(GPRM and SPRM) that support a wide range of problem formulations and cost functions is presented. GPRM, themore\r\ngeneral of the two schemes, reduces the problem to computing a shortest path in a DAG; SPRM, the less general scheme, employs\r\ndynamic programming. Both meta algorithms are linear in n and compute optimal solutions. GPRMcan be exponential in k but is\r\nnevertheless practical because k is typically a small constant.The deterministic quality of this meta algorithm and the guarantee of\r\noptimal solutions for all of the formulations discussed make this approach a powerful alternative to other metatechniques such as\r\nsimulated annealing and genetic algorithms.
Loading....